PREUVE COMPLÈTE DU THÉORÈME PCP<br />Cours de 5x2h par Nicolas Schabanel (CNRS - LIAFA, Université Paris Diderot)<br />%%%%<br />Mardi 14 juin 14h-16h (Partie A)<br /> • Definition de la classe PCP<br /> • Théorème PCP NP-difficulté d'approximer à une constante<br />près un problème de satisfaction de contraintes<br /> • Test de linéarité et auto-correction<br />%%%%%<br />Résumé:<br />En 2006, Irit Dinur a proposé une preuve relativement simple,<br />intuitive et très certainement élégante d'un des théorèmes majeurs de ces<br />vingt dernière années en informatique: le théorème PCP, c'est-à-dire la<br />démonstration que NP = PCP (log n, 1), ou encore qu'il suffit de lire un<br />nombre _constant_ de bits choisis aléatoirement (suivant une distribution<br />adéquate) d'une solution d'un problème NP pour décider si c'est bien une<br />solution valide ou non. Ce théorème a permis en particulier d'étendre les<br />techniques ultra-classiques de NP-difficulté de la résolution exacte de<br />problème NP à la démonstration de leur inapproximabilité, avec un très<br />gros succès puisque de très nombreux résultats donnent le facteur<br />d'approximation exact. Initialement démontré en 1992 avec des méthodes très<br />complexes, la preuve d'Irit Dinur est particulièrement intuitive et<br />satisfaisante pour un algorithmicien, puisqu'elle démontre directement<br />l'inapproximabilité de Max-3SAT en procédant algorithmiquement par<br />amplification itérative du gap dans la réduction de NP à SAT.<br /><br />Je vous propose pendant 5 séances de cours, réparties sur deux jours et demi,<br />de démontrer intégralement ce théorème. Ce sera l'occasion de découvrir et de<br />pratiquer les techniques issues de l'aléatoire maintenant classiques en<br />théorie de la complexité. Nous verrons également les liens étonnants entre<br />preuve, hasard et inapproximabilité.<br /><br />J'ai prévu un volume de 5x2h de cours pour cette démonstration. Les<br />prérequis sont minimes: définition de NP, quelques connaissance de base de<br />probabilités et de graphes. Les cours seront fait au tableau.
